1. Field
The present disclosure relates to digital signal processing. More particularly, this invention is directed toward a fast convolution of a signal with a one-sided exponential function.
2. Description of Related Technology
Many fields of engineering and science utilize convolution of a signal of interest with a kernel comprising a class of symmetric functions. Such a class may comprise, e.g., finite window functions such as cosine window, raised cosine window, Lanczos window with small radius, as well as infinite functions like Gaussian function, Gabor atoms (or functions), specifically designed low pass filters, and other symmetric functions known to a person of ordinary skills in the art.
A convolution of a signal with a kernel comprising Gaussian function finds use in such fields as speech recognition, signal equalization, image processing and other fields known to a person of ordinary skills in the art. By means of an example, an edge detection in a signal comprising an image takes an advantage of the fact that the edges of the objects in the image with a characteristic size or spacing related to the widths of the Gaussian functions appear as zero values. By means of another example, Gabor functions, are frequently used as kernels for time-frequency analysis, e.g., feature extraction, especially in texture-based image analysis (e.g. classification, segmentation or edge detection), iris recognition. By means of yet another example, raised cosine function is frequently used as a kernel in matched filters.
A traditional approach to calculating a convolution is to implement the convolution through direct numerical computation between the signal of interest and the kernel, corresponding to a function from, e.g., the above-discussed class of functions. However, in applications, where computational time is critical, such implementation is not suitable and is desired to be improved.
One approach is disclosed in a document by Seeman, M., Zem{hacek over (e)}ik, P., entitled Histogram Smoothing for Bilateral Filter, Proc. GraVisMa, Plzen, Czech Rep., pp. 145-148, 2009. As disclosed therein, the approach considers a kernel comprising Gaussian function. One half of the Gaussian function is approximated by one or more exponential functions, thus decreasing the computational complexity form (m×n) (where n is the number of signal samples and m is the size of the convolution kernel) to n (where n is the number of the signal samples). The convolution with the exponential function is then calculated in a forward direction, i.e., for signal samples starting with the first sample and then in a reverse direction, i.e., for signal samples starting with the last sample. The result of the forward and reverse calculations are then added together.
A problem with this approach is that due to the need for calculation in a forward and reverse directions, the entire signal must be known in advance; therefore, only post-processing of a signal that has been acquired is feasible.
However, many engineering and scientific processes produce signals, which are not necessary finite, e.g., speech, motion pictures, and other signals known to a person of ordinary skills in the art. Accordingly, there is a need in the art for a fast convolution of a signal with an exponential function, used, e.g., to approximate kernels comprising a class of symmetric functions, thus providing a solution to the above identified problem, enabling calculation of convolution of such kernels with both definite and indefinite signals, as well as providing additional advantages.